home *** CD-ROM | disk | FTP | other *** search
/ MacTech 1 to 12 / MacTech-vol-1-12.toast / Source / MacTech® Magazine / Volume 09 - 1993 / 09.01 Jan 93 / Programmers' Challenge / palindromes.c
Encoding:
C/C++ Source or Header  |  1992-12-03  |  4.9 KB  |  209 lines  |  [TEXT/KAHL]
  1. /* FindNthPalindrome by Stepan Riha
  2.  *
  3.  * This algorithm works with the following
  4.  * fact in mind: An N-digit string can form
  5.  * 9 * 10^((N-1)/2) palindromes:
  6.  *
  7.  *                Odd N:                Even N:
  8.  *    1st        100..000..001        100..0000..001
  9.  *    2nd        100..010..001        100..0110..001
  10.  *    3rd        100..020..001        100..0220..001
  11.  *             100.......001        100........001
  12.  *    10th    100..090..001        100..0990..001
  13.  *    11th    100..101..001        100..1001..001
  14.  *    12th    100..111..001        100..1111..001
  15.  *            .............        ..............
  16.  *    last-1    999..989..999        999..9889..999
  17.  *    last    999..999..999        999..9999..999
  18.  *
  19.  * Speedups are achieved bye replacing x*10
  20.  * with (x<<1 + x<<3) and by doing conversions
  21.  * requireing x/10 and x%10 on my own
  22.  * approximating 1/10 with 3/32. Also, I use
  23.  * a lookup table for powers of 10, etc.
  24.  */
  25.  
  26. /* Precomputed values:
  27.     palins10    is an array of 9*10^((n-1)/2)
  28.     multpow10    is a multiplication table of
  29.                 10^n (last row is all 10^9
  30.                 because of integer overflow)
  31. */
  32.  
  33. static long palins10[] = {
  34.     9L, 9L, 90L, 90L, 900L, 900L, 9000L,
  35.     9000L, 90000L, 90000L, 900000L
  36. };
  37.  
  38. static long multpow10[100] = {
  39.     0L, 1L, 2L, 3L, 4L,
  40.         5L, 6L, 7L, 8L, 9L,
  41.     0L, 10L, 20L, 30L, 40L,
  42.         50L, 60L, 70L, 80L, 90L,
  43.     0L, 100L, 200L, 300L, 400L,
  44.         500L, 600L, 700L, 800L, 900L,
  45.     0L, 1000L, 2000L, 3000L, 4000L,
  46.         5000L, 6000L, 7000L, 8000L, 9000L,
  47.     0L, 10000L, 20000L, 30000L, 40000L,
  48.         50000L, 60000L, 70000L, 80000L, 90000L,
  49.     0L, 100000L, 200000L, 300000L, 400000L,
  50.         500000L, 600000L, 700000L, 800000L,
  51.         900000L,
  52.     0L, 1000000L, 2000000L, 3000000L, 4000000L,
  53.         5000000L, 6000000L, 7000000L, 8000000L,
  54.         9000000L,
  55.     0L, 10000000L, 20000000L, 30000000L,
  56.         40000000L, 50000000L, 60000000L, 70000000L,
  57.         80000000L, 90000000L,
  58.     0L, 100000000L, 200000000L, 300000000L,
  59.         400000000L, 500000000L, 600000000L,
  60.         700000000L, 800000000L, 900000000L,
  61.     0L, 1000000000L, 1000000000L, 1000000000L,
  62.         1000000000L, 1000000000L, 1000000000L,
  63.         1000000000L, 1000000000L, 1000000000L
  64. };
  65.  
  66. /* (x * 10) */
  67. #define Times10(x) ((x<<1) + (x<<3)) 
  68. /* x *= 10 */
  69. #define MultBy10(x) x += x + (x<<3)
  70. /* (x * 3 / 32) */
  71. #define ApproxDiv10(x) ((x>>4)+(x>>5))
  72. /* (x/2) */
  73. #define Half(x) ((x)>>1)
  74.  
  75. long FindNthPalindrome(long baseNumber, short n);
  76.  
  77. long FindNthPalindrome(register long base, short n)
  78. {
  79.     register long    num, dig, mult10, remain,
  80.                     *lop, *hip, *multpow;
  81.     long            buffer[16];
  82.  
  83.     if (base >= 1000000000L)
  84.         /* to big to start with */
  85.         return -1L;
  86.  
  87.     if (!(num = n))
  88.         /* 0th palindrome doesn't exist */
  89.         return base;
  90.  
  91.     /* palindrome =
  92.      *         n-th palindrome > baseNumber */
  93.  
  94.     /* Find dig = (number of digits in
  95.      * baseNumber) - 1
  96.      * Find how many dig-digit palindromes
  97.      * are smaller than the baseNumber
  98.      */
  99.  
  100.     if (base < 10) { /* baseNumber <= 9 */
  101.         dig = 0;
  102.         /* all 1-digit strings are
  103.          * palindromes (duh!)
  104.          */
  105.         num += base - 1; 
  106.     }
  107.     else { /* baseNumber is >= 10 */
  108.         /* Convert baseNumber to string.
  109.          * This is faster than using /1
  110.          * and %10
  111.          */
  112.         lop = buffer; dig = -1;
  113.         while (base) {
  114.             remain = base; base = 0;
  115.             goto division1;
  116.             while (mult10) {
  117.                 base += mult10;
  118.                 remain -= Times10(mult10);
  119.             division1:
  120.                 mult10 = ApproxDiv10(remain);
  121.             }
  122.             if (remain >= 10) {
  123.                 base++; remain -= 10;
  124.             }
  125.             *lop++ = remain; dig++;
  126.         }
  127.         /* Find how many dig-digit palindromes
  128.          * are smaller than this string
  129.          * Start searching from the middle
  130.          */
  131.         hip = (lop = buffer) + Half(dig+1);
  132.         lop += (base = Half(dig));
  133.         multpow = multpow10;
  134.         for(; base >= 0 && *lop==*hip;
  135.           hip++, lop--, multpow += 10, base--)
  136.             num += multpow[*hip];
  137.         if (base >= 0) {
  138.             if (*hip > *lop)
  139.                 num--;
  140.                 for(; base >= 0;
  141.                   hip++, multpow += 10, base--)
  142.                     num += multpow[*hip];
  143.         }
  144.         /* adjust for no leading zero */
  145.         num -= multpow[-9]; 
  146.     } /* if (baseNumber < 10) */
  147.  
  148.     /* palindrome =
  149.      *        num-th palindrome > 10^dig */
  150.  
  151.     /* Find how many digits the palindrome
  152.      * will have
  153.      */
  154.     hip = (lop = palins10) + dig;
  155.     while (num >= 0)
  156.         num -= *hip++;
  157.     num += *(--hip);
  158.     dig = hip - lop;
  159.     if (dig >= 9)
  160.         /* i.e. baseNumber > 999999999
  161.          * (dig is always <= 10) */
  162.         return -1L;
  163.  
  164.     /* palindrome =
  165.      *        num-th dig-digit palindrome */
  166.  
  167.     /* Find the num-th dig-digit paindrome.
  168.      * Calculate final palindrome string. This
  169.      * is faster than using /10 and %10
  170.      * Use lop and hip to point in the correct
  171.      * row in the multiplication table
  172.      * Start filling digits from the middle of
  173.      * the string
  174.      */
  175.     base = Half(dig+1);
  176.     hip = (lop = multpow10) + Times10(base);
  177.     base = Half(dig);
  178.     lop += Times10(base);
  179.     base = 0L;
  180.     while (num) {
  181.         remain = num; num = 0;
  182.         goto division2;
  183.         while (mult10) {
  184.             num += mult10;
  185.             remain -= Times10(mult10);
  186.         division2:
  187.             mult10 = ApproxDiv10(remain);
  188.         }
  189.         if (remain >= 10) {
  190.             num++; remain -= 10;
  191.         }
  192.         base += lop[remain];
  193.         if (lop < hip)
  194.             /* don't count middle digit twice */
  195.             base += hip[remain];
  196.         lop -= 10; hip += 10;
  197.     }
  198.     /* adjust for no leading zero */    
  199.     lop = multpow10 + 1; 
  200.     base += *lop;
  201.     if (dig) {
  202.         MultBy10(dig);
  203.         base += lop[dig];
  204.     }
  205.  
  206.     return base;
  207. }
  208.  
  209.